UVa/10819 - Trouble of 13-Dots/10819.cpp

   1 #include <iostream>
   2 #include <stdio.h>
   3 using namespace std;
   4
   5 const int MAXN = 100, MAXM = 10205;
   6
   7 int dp[MAXN][MAXM+1], p[MAXN], v[MAXN];
   8
   9
  10
  11 int main(){
  12   int n, m;
  13   while (scanf("%d %d", &m, &n) == 2){
  14     if (n == 0){
  15       printf("0\n");
  16       continue;
  17     }
  18     int old_m = m;
  19     m += 200;
  20     for (int i=0; i<n; ++i) scanf("%d %d", &p[i], &v[i]);
  21
  22     dp[0][0] = 0;
  23     for (int j=1; j<=m; ++j) dp[0][j] = INT_MIN;
  24     dp[0][p[0]] = v[0];
  25     for (int i=1; i<n; ++i){
  26       for (int j=0; j<=m; ++j){
  27         dp[i][j] = dp[i-1][j];
  28         if (j - p[i] >= 0 && dp[i-1][j-p[i]] >= 0){
  29           dp[i][j] = max(dp[i][j], dp[i-1][j-p[i]] + v[i]);
  30         }
  31       }
  32     }
  33
  34     int ans = 0;
  35     for (int j=0; j<=old_m; ++j){
  36       ans = max(ans, dp[n-1][j]);
  37     }
  38     for (int j=2001; j<=old_m+200; ++j){
  39       ans = max(ans, dp[n-1][j]);
  40     }
  41     printf("%d\n", ans);
  42   }
  43   return 0;
  44 }